Communications networks currently transfer vast quantities of information in both local and wide area networks The information typically consists of signals (electronic or optical) representing digitized or digital voice, video, and/or data that is transferred between endpoints in networks. For information to be transmitted in a network, a communication path must be established within the network between the sender(s) and receiver(s) of the information. A communication path may be established by circuit switching, wherein an exclusive channel is established between the sender(s) and receiver(s) throughout the entire transmission and until the connection is released. Alternatively, a communication path may be established by packet switching, wherein virtual circuits or channels are established between sender(s) and receiver(s) and with the channel only occupied for the duration of transmission of the packet.
Packet switching enables networks to handle the heterogenous mix of network traffic with varying service requirements that are encountered in Broadband Integrated Services Digital Networks (B-ISDN). Ideally, packet switching is scalable and can reliably establish and maintain virtual channels without any prespecified rates (so-called bandwidth on demand). Asynchronous Transfer Mode (ATM) is a connection oriented network technology that provides a possible framework for ideal packet switching that is designed to support multiple classes (e.g., voice, video, data) of traffic.
In ATM, information is transmitted as packets of digital information called cells. Each cell includes 53 bytes of digital information, ATM is connection oriented; a connection is formed between the transmitter(s) and receiver(s) where each intermediate switch in the virtual circuit or channel (VC) is aware of the service requirements and traffic parameters of the connection. The links between switches are "virtual" only in that each link may be shared by several connections on a demand basis instead of a fixed allocation of the entire link to a single connection as in a circuit-switched network. By making each switch aware of the service requirements and traffic parameters for each connection, the quality of service (QOS) of the channel can be guaranteed by the network if the connection stays within its stated traffic parameters.
The quality of service in an ATM-switched network typically refers to the probability of a cell being dropped, (cell loss) and factors affecting cell delivery timeliness, particularly cell delay and cell delay variation. Traffic parameters typically refer to the rate at which data bits are transmitted through the network (bit rate) and the variations in the bit rate (burstiness). Different classes of traffic require different levels of QOS and have different traffic parameters. For example, voice communications are typically transmitted at a continuous bit rate (CBR) of 64 Kbit/second with no burstiness and can tolerate some cell loss but little delay. Another example is compressed packetized voice or video which is transmitted at a variable bit rate (VBR) with varying degrees of burstiness and bounded limits on delay because of the need to reconstruct the video or voice. Computer file transfer and data network applications, on the other hand, will generate data at widely varying rates without stringent requirements regarding cell delay and may be readily transmitted whenever bandwidth is available in the channel at the available bit rate (ABR). Available Bit Rate traffic may also be classified as Unspecified Bit Rate (UBR) if no minimum cell rate is declared.
The QOS of a connection in an ATM switched network may be "guaranteed" by "contract" when a connection is established through a process of connection admission control (CAC). Essentially, each connection "contracts" to transmit cells to the network at a rate .rho. (bandwidth descriptor) with burstiness .sigma. (burst descriptor) when the connection is established. The network will not allow the connection to be established if there are insufficient network resources (e.g., buffer and/or bandwidth) to provide the required QOS at the contracted traffic parameters.
Once connections have been established, the connections have to be regulated to prevent congestion in the network. Although each connection is expected to comply with the contracted traffic parameters, it is necessary for the network to ensure compliance by the connection. Prior art techniques for regulating connections (traffic control) include policing the connection and discarding excess cells (i.e., cells violating the contracted traffic parameters) seeking to enter the network. See, e.g., Boyer, P., "A Congestion Control for the ATM," Proc. 7th ITC Spec. Seminar, Paper 4.3, New Jersey, October, 1990 (Describing pick-up policing algorithms). Prior art techniques have also suggested policing by tagging the cell loss priority (CLP) bit of non-compliant cells and only discarding the cells if the network becomes sufficiently congested to adversely affect network performance.
Traffic shaping is another form of traffic control for ATM switched networks. Traffic shaping can be used to ensure compliance with the traffic contract when applied at the edge of the network or, if applied within the network interior, to normalize traffic and limit jitter by reshaping connections and spacing cells. So-called "leaky bucket traffic shaping" is often used in ATM switched networks. In a typical prior art leaky bucket traffic shaper, credit "tokens" are provided by the traffic shaper at a rate .rho. that represents the sustainable bandwidth for the connection. For example, tokens could be provided at a rate of one token every ten time slots, where a time slot represents the minimum time for a cell to leave the traffic shaper. In other words, a fully utilized traffic shaper would transmit one cell every time slot. These credit tokens accumulate in a "leaky bucket" that holds up to .sigma. (burst size) credit tokens. Each cell arriving at the traffic shaper must claim a token to pass through the shaper; if no tokens are available, the cell is considered "nonconforming" and is delayed until a token is available when the connection conforms to the traffic contract.
A traffic shaper determines whether an arriving cell conforms to its connection's traffic parameters or descriptors using any of a variety of algorithms known in the art, the most common of which is the generic cell rate algorithm (GCRA) from the ATM Forum. The GCRA computes conformance based on a connection's shaping rate and burstiness and when the last cell arrived at the shaper from that connection.
Cells are scheduled for transmission from a traffic shaper based on the cell's conformance times. In typical prior art traffic shapers, cells are sorted in exact order of conformance times. One prior art implementation is a shift register wherein the sorted cells (or pointers) are stored and appropriately shifted when a cell with an intermediate conformance time is added. This implementation is disadvantageous because of the prohibitive hardware costs incurred by parallel comparison operations and additional circuitry needed to compensate for clock rollovers.
An alternative prior art traffic shaper avoided these drawbacks by implementing the scheduler as a series of bins corresponding to single transmission slots. By traversing the bins at the transmission, the traffic shaper can transmit one cell at each time slot if there is a cell awaiting transmission in the bin. If the bin is empty then a cell will not be transmitted during that time slot. This traffic shaper puts an arriving cell into the first bin that corresponds to or follows its conformance time. There are, however, several disadvantages with this implementation. Complex logic is required to locate an appropriate empty bin and, under heavy traffic conditions a cell may be scheduled for transmission far after its conformance time. Moreover, early arrivals inherently receive preferential treatment at the expense of cells arriving from connections adhering to traffic contract parameters.
Some of these disadvantages have been addressed by another prior art traffic shaper using a calendar queue where each bin corresponds to a linked list of cells having a particular conformance time instead of a single cell. In this implementation, a cell is merely appended to the linked list corresponding to its conformance time. Because only one cell may be transmitted at a time, an additional transmit queue is required to enqueue multiple cells for output. This implementation does reduce the need for a complex exact priority queue, but also has several disadvantages.
The primary disadvantage is the need to accomodate the maximum possible number of conformance times while accounting for switch capacity limitations and the resultant possibility of dropping non-conforming cells. Although it has been suggested that a range of consecutive conformance times could be associated with each bin to reduce the number of bins, (i.e., bin granularity&gt;1), large bin granularity creates excessive jitter distorting traffic parameters, especially in high bandwidth connections. Moreover, this implementation does not mediate between multiple connections with simultaneously conforming cells.
A traffic shaper with multiple incoming connections can quickly develop a backlog of conforming cells simultaneously eligible for transmission. Prior art techniques for arbitrating amongst the simultaneously conforming cells have proven inadequate, frequently increasing cell-shaping delays and distorting connection parameters for all cells, even cells that conformed upon arrival. These problems can propagate through the network, violating traffic descriptors for downstream switches and further increasing delay and loss. Constant bit rate and real-time variable bit rate connections are particularly impacted because of the inherent low tolerance for delay variations.
Prior art traffic policing and shaping techniques are proving to be inadequate for B-ISDN and the heterogenous traffic of contemporary networking, resulting in traffic distortions and congestion. In particular, the prior art techniques do not efficiently handle numerous traffic classes while fairly distributing network resources amongst several connections. The unique difficulties encountered when attempting to shape traffic from several connections with widely varying rates are not adequately handled by prior art policers and shapers. For example, prior art policers are unsuitable for responding to momentary violations of contract parameters by connections that are fully compliant over the long term, resulting in avoidable packet loss or traffic disruption. Many proposed techniques for fairly distributing network resources cannot be readily implemented because they are not readily scalable or impose unacceptable costs (e.g., switching delays or hardware implementation complexity) Without efficient and scalable techniques for traffic shaping, the potential of ATM switched networks cannot be realized.